class Solution {
public:
    int integerBreak(int n) {
        // 初始化记忆化数组 cache，大小为 n+1，初始值为 -1
        // cache[i] 用于存储拆分 i 的最大乘积
        auto cache = vector<int>(n+1, -1);

        // 定义 dfs 函数，采用 lambda 表达式递归方式进行记忆化搜索
        // self 用于引用 dfs 函数本身，从而支持递归
        auto dfs = [&](auto&& self, int k) -> int {
            // 边界条件：当 k == 1 时，无法再拆分，只能返回 1
            if (k == 1) return 1;

            // 如果 cache[k] 已经计算过，则直接返回缓存值，避免重复计算
            if (cache[k] != -1) {
                return cache[k];
            }

            // 计算最大乘积
            int ans = 0;
            // 遍历所有可能的拆分方式，将 k 拆成 x 和 y (x + y = k)
            for (int i = 1; i <= k - 1; i++) {
                int x = i, y = k - i;  // 拆分成 x 和 y
                // 计算拆分后的最大乘积
                // 比较两种情况：
                // 1. x * y：直接计算 x 和 y 的乘积
                // 2. x * self(self, y)：计算 y 的最大乘积，递归调用 dfs
                ans = max(ans, max(x * y, x * self(self, y)));
            }

            // 将计算得到的最大乘积存入 cache[k]
            cache[k] = ans;
            return ans;
        };

        // 调用 dfs 函数计算 n 的最大乘积
        return dfs(dfs, n);
    }
};
